package com.leetcode.algorithm.y22.m08.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 230. 二叉搜索树中第K小的元素
 * 
 * https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
 * 
 * @author jie.deng
 *
 */
class Question0230Solution01 {

	public int kthSmallest(TreeNode root, int k) {
		return inorderTraversal(root, new int[] { k });
	}

	private int inorderTraversal(TreeNode cur, int[] arr) {
		if (cur == null) {
			return -1;
		}
		int ret = inorderTraversal(cur.left, arr);
		if (ret != -1) {
			return ret;
		}
		arr[0] -= 1;
		if (arr[0] == 0) {
			return cur.val;
		}
		return inorderTraversal(cur.right, arr);
	}

}